package com.melo;

import lombok.Data;

import java.util.Arrays;

/**
 * @Author lichunlong lcl253137@alibaba-inc.com
 * @Desc 克鲁斯卡尔算法: 解决公交站之间的联通问题
 * @Date 2025-05-25
 */
@Data
public class Kruskal {

    /**
     * 公交站之间边的个数
     */
    private int edgeSize;

    /**
     * 公交站之间修路途径的公交站顶点集合
     */
    private char[] vertexArr;

    /**
     * 邻接矩阵: 两个点确定一条边, 权值表示距离
     */
    private int[][] matrixArr;

    /**
     * 两个不能连通顶点之间的权值
     */
    public static final int DIS_CONNECTED_WEIGHT = Integer.MAX_VALUE;

    public Kruskal(char[] vertexArr, int[][] matrixArr) {
        int vertexSize = vertexArr.length;
        // 初始化顶点
        this.vertexArr = new char[vertexSize];
        System.arraycopy(vertexArr, 0, this.vertexArr, 0, vertexArr.length);

        // 初始化边
        this.matrixArr = new int[vertexSize][vertexSize];
        for (int i = 0; i < vertexSize; i++) {
            System.arraycopy(matrixArr[i], 0, this.matrixArr[i], 0, vertexSize);
        }

        // 统计边的条数
        for (int i = 0; i < vertexSize; i++) {
            for (int j = i + 1; j < vertexSize; j++) {
                if (this.matrixArr[i][j] != DIS_CONNECTED_WEIGHT) {
                    edgeSize++;
                }
            }
        }
    }

    public void kruskal() {
        // "已有最小生成树"中的每个顶点在最小生成树中的终点
        int[] vertexEndArr = new int[edgeSize];
        // 最终的最小生成树结果
        Edge[] resultEdgeArr = new Edge[edgeSize];
        // 最后结果数组resultEdgeArr的索引
        int index = 0;

        // 获取图中所有边的集合: 本案例中一共有12边
        Edge[] edgeArr = listEdge();
        System.out.println("图中边的集合=" + Arrays.toString(edgeArr) + "; 共" + edgeArr.length + "条边");
        // 按边的权值从小到大排序
        bubbleSortEdge(edgeArr);

        for (int i = 0; i < edgeSize; i++) {
            // 获取到第i条边的第一个顶点: 起点
            int edgeStartVertexIndex = getVertexIndex(edgeArr[i].getStartVertex());
            // 获取到第i条边的第2个顶点: 终点
            int edgeEndVertexIndex = getVertexIndex(edgeArr[i].getEndVertex());

            // 获取edgeStartVertexIndex顶点在已有最小生成树中的终点
            int edgeStartVertexMatchEndVertexIndex = getVertexEnd(vertexEndArr, edgeStartVertexIndex);
            // 获取edgeEndVertexIndex顶点在已有最小生成树中的终点
            int edgeEndVertexMatchEndVertexIndex = getVertexEnd(vertexEndArr, edgeEndVertexIndex);
            // 判断是否构成回路: 没有构成回路
            if (edgeStartVertexMatchEndVertexIndex != edgeEndVertexMatchEndVertexIndex) {
                // 设置edgeStartVertexMatchEndVertexIndex在"已有最小生成树"中的终点<E,F> [0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0]
                vertexEndArr[edgeStartVertexMatchEndVertexIndex] = edgeEndVertexMatchEndVertexIndex;
                resultEdgeArr[index++] = edgeArr[i];
            }
        }

        System.out.println("最小生成树为");
        for(int i = 0; i < index; i++) {
            System.out.println(resultEdgeArr[i]);
        }
    }

    /**
     * 打印邻接矩阵
     */
    public void showMatrix() {
        System.out.println("邻接矩阵为: \n");
        for (int i = 0; i < vertexArr.length; i++) {
            for (int j = 0; j < vertexArr.length; j++) {
                System.out.printf("%12d", matrixArr[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 对边进行冒泡排序
     *
     * @param edgeArr 边的集合
     */
    public void bubbleSortEdge(Edge[] edgeArr) {
        for (int i = 0; i < edgeArr.length - 1; i++) {
            for (int j = 0; j < edgeArr.length - 1 - i; j++) {
                if (edgeArr[j].getWeight() > edgeArr[j + 1].getWeight()) {
                    Edge tempEdge = edgeArr[j];
                    edgeArr[j] = edgeArr[j + 1];
                    edgeArr[j + 1] = tempEdge;
                }
            }
        }
    }

    /**
     * 获取顶点的下标
     *
     * @param vertex 顶点的值，比如'A','B'
     * @return 顶点对应的下标，如果找不到，返回-1
     */
    private int getVertexIndex(char vertex) {
        for (int i = 0; i < vertexArr.length; i++) {
            if (vertexArr[i] == vertex) {
                return i;
            }
        }
        // 找不到, 返回-1
        return -1;
    }

    /**
     * 通过matrixArr邻接矩阵来获取图中边
     *
     * @return 边的集合; 形式[['A','B', 12], ['B','F',7], ...]
     */
    public Edge[] listEdge() {
        int index = 0;
        Edge[] edgeArr = new Edge[edgeSize];
        for (int i = 0; i < vertexArr.length; i++) {
            for (int j = i + 1; j < vertexArr.length; j++) {
                if (matrixArr[i][j] != DIS_CONNECTED_WEIGHT) {
                    edgeArr[index++] = new Edge(vertexArr[i], vertexArr[j], matrixArr[i][j]);
                }
            }
        }

        return edgeArr;
    }

    /**
     * 获取下标为vertexStartIndex顶点对应的终点, 用于判断两个顶点的终点是否相同
     *
     * @param vertexEndArr     记录了各个顶点对应的终点
     * @param vertexStartIndex 传入顶点对应的下标
     * @return 下标为vertexStartIndex顶点对应终点的下标
     */
    private int getVertexEnd(int[] vertexEndArr, int vertexStartIndex) {
        while (vertexEndArr[vertexStartIndex] != 0) {
            vertexStartIndex = vertexEndArr[vertexStartIndex];
        }
        return vertexStartIndex;
    }
}
